package Tree;

import java.util.LinkedList;
import java.util.Queue;

public class IsCompleteTree {

	public static void main(String[] args) {
		int[] pre = {5, 4, 8, 10, 11, 6, 9, 3, 7};
		int[] in = {10, 8,11, 4, 6, 5, 3, 9, 7};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		IsCompleteTree object = new IsCompleteTree();
		System.out.println(object.isFullTree_2(root));
	}
	
	
	//判断是否是完全二叉树
	//我们知道完全二叉树就是只有最后一行有空结点，中间没有，所以我们采用广度优先遍历的时候，一旦遇到空结点我们就停下
	//然后判断是否后面还有非空的结点，如果有，则返回false
	public boolean isCompleteTree(TreeNode root){
		if(root == null){
			return true;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		
		queue.add(root);
		//比如
		//     5
		//  1     2
		// 3  6  4  9
		//7 8
		while(queue.peek() != null){
			TreeNode temp = queue.poll();
			queue.add(temp.left);
			queue.add(temp.right);
		}
		//上面的树结构没有非空结点，所以肯定会在8被 pop之后遇到null，然后循环退出
		//此时队列中全为null，所以会返回true
		while(!queue.isEmpty()){
			//如果遇到非空结点我们就知道在该非空结点前遇到了空结点，这是不满足条件的
			//直接返回false
			if(queue.poll() != null){
				return false;
			}
		}
		return true;
	}
	
	//判断是否是满二叉树, 错误代码
	@Deprecated
	private boolean isFullTree(TreeNode root){
		if(root == null){
			return true;
		}
		if(root.left == null && root.right == null){
			return true;
		}
		//不对...
		//我们没有判断左子树跟右子树的深度是否是一样的
		//比如      5
		//   4    9
		// 8   6
		//会返回true
		if(root.left != null && root.right != null){
			return isFullTree(root.left) && isFullTree(root.right);
		}
		return false;
	}
	
	//判断是否是满二叉树
	public boolean isFullTree_2(TreeNode root){
		if(root == null){
			return true;
		}
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		int index = 0;
		while(queue.get(index) != null){
			//我们这个时候先不出队
			//不出队我们怎么广度优先遍历的啊...不会啊
			//TreeNode temp = queue.getLast();
			//不知道是不是这样的...
			TreeNode temp  = queue.get(index++);
			queue.add(temp.left);
			queue.add(temp.right);
		}
		int cur = 1;
		while(!queue.isEmpty()){
			//每一层应该出队的是1  2  4  8...
			//如果没有出队的就为空了，那么肯定不是满二叉树
			int length = 0;
			while(length < cur){
				if(queue.isEmpty()){
					return false;
				}else{
					queue.poll();
					length++;
				}
			}
			cur = cur << 1;
		}
		return true;
	}
	
	public boolean isFullTree_3(TreeNode root){
		if(root == null){
			return true;
		}
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		//我们定义左右结点都不为null的满结点
		//如果不满足，则记为非满结点
		//flag表示是否找到非满结点
		boolean flag = false;
		while(!queue.isEmpty()){
			//我们这个时候先不出队
			TreeNode temp = queue.poll();
			if(flag){
				if(temp.left != null || temp.right != null){
					return false;
				}
			}else{
				if(temp.left != null && temp.right != null){
					queue.add(temp.left);
					queue.add(temp.right);
				}else if(temp.right != null || temp.left != null){
					//如果只存在左、右孩子，则，一定不满足满二叉树  
	                return false;    
				}else{
	                flag = true;    
	        	}    
			}
		}
		return true;
	}
}
